package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

import static xyz.scootaloo.oj.ds.helper.CollectionBuilder.intArr;

/**
 * 动态规划
 *
 * @author flutterdash@qq.com
 * @since 2021/3/26 21:51
 */
public class P304 {

    private static class NumMatrix {

        private final int[][] dp;

        public NumMatrix(int[][] matrix) {
            int row = matrix.length;
            int column = matrix[0].length;
            dp = new int[row][column];
            System.arraycopy(matrix[0], 0, dp[0], 0, column);
            for (int r = 1; r<row; r++) {
                for (int c = 0; c<column; c++) {
                    dp[r][c] = matrix[r][c] + dp[r - 1][c];
                }
            }
        }

        /**
         * [1] 1  1  1
         *  1  1 [1] 1
         *  1  1  1  1
         * @return -
         */
        public int sumRegion(int row1, int col1, int row2, int col2) {
            long sum = 0;
            for (int c = col1; c<=col2; c++)
                sum = sum + dp[row2][c];
            if (row1 > 0) {
                row1 -= 1;
                long lowSum = 0;
                for (int c = col1; c<=col2; c++)
                    lowSum = lowSum + dp[row1][c];
                sum -= lowSum;
            }
            return (int) sum;
        }

        private int test(int[] ints) {
            return sumRegion(ints[0], ints[1], ints[2], ints[3]);
        }

    }

    public static void main(String[] args) {
        int[][] input_1 = {
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5}
        };
        NumMatrix matrix = new NumMatrix(input_1);
        Tester.createTest(matrix::test)
                .addCase(intArr(2, 1, 4, 3), 8)
                .addCase(intArr(1, 1, 2, 2), 11)
                .addCase(intArr(1, 2, 2, 4), 12)
                .test();
    }

}
